As the high performance computing systems scale up, mapping the tasks of a parallel application onto physical processors to allow efficient communication becomes one of the challenging problems. Many mapping techniques have been developed to improve the application communication performance. First, graph embedding has been studied and applied to optimize very large scale integrated (VLSI) circuits. See, e.g., John A. Ellis. Embedding rectangular grids into square grids. IEEE Trans. Comput., 40(1):46-52, 1991; Rami G. Melhem and Ghil-Young Hwang. Embedding rectangular grids into square grids with dilation two. IEEE Trans. Comput., 39(12):1446-1455, 1990. The graph embedding for VLSI circuits tries to minimize the longest path.
Second, space filling curves (See, e.g., Space-Filling Curves. Springer-Verlag, 1994) are applied to map parallel programs onto parallel computing systems. The use of space filling curves to improve proximity for mapping is well studied and has found useful in parallel computing. The paper, Masood Ahmed and Shahid Bokhari. Mapping with space filling surfaces. IEEE Trans. Parallel Distrib. Syst., 18:1258-1269, September 2007, extends the concept of space filling curves to space filling surfaces. It describes three different classes of space filling surfaces and calculates the distance between facets.
There are methods using graph-partitioning and search-based optimization to solve the mapping problem. For example, G. Bhanot, A. Gara, P. Heidelberger, E. Lawless, J. C. Sexton, and R. Walkup. Optimizing task layout on the blue gene/l supercomputer. IBM Journal of Research and Development, 49(2):489-500, March 2005, uses an off-line simulated annealing to explore different mappings on Blue Gene/L™.
The work in Hao Yu, I-Hsin Chung, and Jose Moreira. Topology mapping for blue gene/l supercomputer. In SC '06: Proceedings of the 2006 ACM/IEEE conference on Supercomputing, page 116, New York, N.Y., USA, 2006. ACM, developed topology mapping libraries. The mapping techniques are based on folding heuristics. The methods based on folding heuristics require the topologies for guest and host are known already.
Recently, new mapping techniques have been developed. See, e.g., Abhinav Bhatel´e, Eric Bohm, and Laxmikant V. Kal´e. A case study of communication optimizations on 3d mesh interconnects. In Euro-Par '09: Proceedings of the 15th International Euro-Par Conference on Parallel Processing, pages 1015-1028, Berlin, Heidelberg, 2009. Springer-Verlag.
In terms of supporting message passing interface (MPI) topology functions, there are works done for specific systems: Jesper Larsson Tr{umlaut over ( )}aff. Implementing the mpi process topology mechanism. In Supercomputing, pages 1-14,2002, uses graph-partitioning based for embedding and Sangman Moh, Chansu Yu, Dongsoo Han, Hee Yong Youn, and Ben Lee. Mapping strategies for switch-based cluster systems of irregular topology. In 8th IEEE International Conference on Parallel and Distributed Systems, Kyongju City, Korea, June 2001, describes embedding techniques for switch-based network.